'''
https://leetcode.cn/problems/maximum-subarray/description/
'''

from typing import List
class Solution:

    def maxSubArray(self, nums: List[int]) -> int:
        n = len(nums)
        dp = [0] * n
        dp[0] = nums[0]
        for i in range(1, n):
            dp[i] = max(nums[i] + dp[i - 1], nums[i])
        return max(dp)

    def maxSubArray2(self, nums: List[int]) -> int:
        n = len(nums)
        a = nums[0]
        ans = a
        for i in range(1, n):
            b = max(nums[i] + a, nums[i])
            ans = max(ans, b)
            a = b
        return ans

    def maxSubArray3(self, nums: List[int]) -> int:
        n = len(nums)
        a = nums[0]
        ans = a
        for i in range(1, n):
            a = max(nums[i] + a, nums[i])
            ans = max(ans, a)
        return ans